/**
 * 背包问题:给定一个固定大小 能够携重W的背包 以及一组有价值和重量的物品 找出一个最佳解决方案 使得装入背包的物品总重量不超过w 且总价值最大
 * @param {*} capacity 背包容量
 * @param {*} weights 物品的重量
 * @param {*} values  物品的价值
 * @param {*} n 
 * @returns 
 */
function knapSack (capacity, weights, values, n) {
  var i, w, a, b, KS = []
  for (i = 0; i <= n; i++) {
    KS[i] = []
  }
  for (i = 0; i <= n; i++) {
    for (w = 0; w <= capacity; w++) {
      if (i == 0 || w == 0) { // 只处理索引不为0的列和行
        KS[i][w] = 0
      } else if (weights[i - 1] <= w) {
        a = values[i - 1] + KS[i - 1][w - weights[i - 1]]
        b = KS[i - 1][w]
        KS[i][w] = (a > b) ? a : b // max(a,b) 当找到可以构成解决方案的物品时 选择价值最大的那个
      } else {
        KS[i][w] = KS[i - 1][w] // 问题的解决方案在二维表右下角的最后一个格子
      }
    }
  }
  findValues(n, capacity, KS, weights, values)
  return KS[n][capacity]
}
function findValues (n, capacity, KS, weights, values) {
  var i = n, k = capacity
  while (i > 0 && k > 0) {
    if (KS[i][k] !== KS[i - 1][k]) {
      console.log('物品' + i + ',重量' + weights[i - 1] + ',价值' + values[i - 1]);
      i--
      k = k - KS[i][k]
    } else {
      i--
    }
  }
}
var values = [3, 4, 5], weights = [2, 3, 4], capacity = 5, n = values.length
console.log(knapSack(capacity, weights, values, n));